#define _CRT_SECURE_NO_WARNINGS 1
/*
*	随即链表的复制——深度拷贝
*/

struct Node* copyRandomList(struct Node* head)
{
    //将copy节点连接到原节点的后面
    struct Node* cur = head;
    while (cur)
    {
        //创建copy节点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        if (copy == NULL)
        {
            perror("malloc");
            exit(-1);
        }
        copy->val = cur->val;

        //连接copy节点到原链表中
        copy->next = cur->next;
        cur->next = copy;

        //让cur走向下一个待copy的节点
        cur = cur->next->next;
    }

    //设置copy节点的random指针
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        //让cur走到下一个节点
        cur = cur->next->next;
    }

    //将copy节点从原链表剪下来
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
        if (copyhead == NULL)
        {
            //新链表为空
            copyhead = copy;
            copytail = copy;
        }
        else
        {
            //新链表不为空
            //尾插
            copytail->next = copy;
            copytail = copy;
        }
        cur->next = copy->next;//恢复原链表
        cur = cur->next;//让cur走到下一个节点
    }
    return copyhead;
}